package week07

// 684. 冗余连接
// https://leetcode-cn.com/problems/redundant-connection/

func findRedundantConnection(edges [][]int) []int {
	var n = 0
	for _, edge := range edges {
		n = max(n, edge[0], edge[1])
	}

	var father = make([]int, n+1)
	for i := range father {
		father[i] = i
	}

	for _, edge := range edges {
		if find(father, edge[0]) == find(father, edge[1]) {
			return edge
		}
		unionSet(father, edge[0], edge[1])
	}

	return []int{}
}

func find(father []int, x int) int {
	if father[x] != x {
		father[x] = find(father, father[x])
	}
	return father[x]
}

func unionSet(father []int, x, y int) {
	father[find(father, y)] = find(father, x)
}

func max(x int, vals ...int) int {
	for _, val := range vals {
		if val > x {
			x = val
		}
	}
	return x
}